package Z.dailyExercise._0112;

import java.util.*;

public class _1710_卡车上的最大单元数 {

    /**
     * 自解：为了在不超过truckSize的前提下 的到单元的最大数
     * 所以就首先对承载单元进行排序 借助treemap key是类型 value为单元量
     * 从大到小依次取值
     * ==13 5==不用利用map进行排序 直接用Arrays。sort
     * @param boxTypes
     * @param truckSize
     * @return
     */
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Map<Integer,Integer> map = new TreeMap<>();
        for(int i=0;i< boxTypes.length;i++){
            map.put(i,boxTypes[i][1]);
        }

        List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });

        int count =0;
        int maxUnits=0;
        for (Map.Entry<Integer,Integer> e:list){
                int i = e.getKey();
                count += boxTypes[i][0];

                if (count>truckSize){
                    count -= boxTypes[i][0];
                    maxUnits += (truckSize-count)*boxTypes[i][1];
                    break;
                }else {
                    maxUnits += boxTypes[i][0]*boxTypes[i][1];
                }

        }

        return maxUnits;



    }

    /**
     * 改进 不用map了
     * @param boxTypes
     * @param truckSize
     * @return
     */
    public int maximumUnits1(int[][] boxTypes, int truckSize) {

        Arrays.sort(boxTypes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });

        int count =0;
        int maxUnits=0;
        for (int[] box:boxTypes){

            count += box[0];
            if (count>truckSize){
                count -= box[0];
                maxUnits += (truckSize-count)*box[1];
                break;
            }else {
                maxUnits += box[0]*box[1];
            }

        }
        return maxUnits;


    }


}
